package club.xiaojiawei.linkedlist;

import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Objects;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 2022/4/24 下午7:13
 * @question 面试题 02.07. 链表相交
 * @description 给你两个单链表的头节点headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * 图示两个链表在节点 c1 开始相交：
 * 给你两个单链表的头节点headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
 * 图示两个链表在节点 c1 开始相交：
 */

public class LinkedLIstIntersect0207 {

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);

        ListNode head2 = new ListNode(7);
        head2.next = new ListNode(9);
        head2.next.next = new ListNode(3);
        head2.next.next.next = new ListNode(4);

//        ListNode result = getIntersectionNode(head, head2);
        ListNode result = getIntersectionNode2(head, head2);
        System.out.println(result);
    }

    /**
     * HashSet检测是否重复
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        HashSet<ListNode> set = new HashSet<>();
        ListNode temp = headA;
        while (temp != null){
            set.add(temp);
            temp = temp.next;
        }
        temp = headB;
        while (temp != null){
            if (set.contains(temp)){
                return temp;
            }
            temp = temp.next;
        }
        return null;
    }

    /**
     * 民间-双指针，环形链表思路
     * @param headA
     * @param headB
     * @return
     */
    public static ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
//        有一方为null则必然不可能相交
        if (headA == null || headB == null){
            return null;
        }
        ListNode tempA = headA;
        ListNode tempB = headB;
//        while终止的两种条件：1 temA和tempB都为null，即两个指针把环形链表遍历了一圈还没找到相同的node；2 找到相同的node了
        while (!Objects.equals(tempA, tempB)){
            tempA = (tempA == null? headB : tempA.next);
            tempB = (tempB == null? headA : tempB.next);
        }
        return tempA;
    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    '}';
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            ListNode listNode = (ListNode) o;
            return val == listNode.val;
        }

        @Override
        public int hashCode() {
            return Objects.hash(val);
        }
    }
}
